import json
from collections import deque
import heapq
import os

class Book:
    """
    图书类：存储图书的基本信息
    属性包括：标题、作者、出版社、年份、类别、子类别、语言、页数、关键词、摘要和借阅次数
    """
    def __init__(self, title, authors, publisher, year, category, sub_category, language, page_count, keywords, summary):
        self.title = title
        self.authors = authors
        self.publisher = publisher
        self.year = year
        self.category = category
        self.sub_category = sub_category
        self.language = language
        self.page_count = page_count
        self.keywords = keywords
        self.summary = summary
        self.borrow_count = 0
        self.is_borrowed = False  # 添加借阅状态

class AVLNode:
    """
    AVL树节点类：用于构建平衡二叉搜索树
    包含图书对象、左右子节点和节点高度
    """
    def __init__(self, book):
        self.book = book
        self.left = None
        self.right = None
        self.height = 1

class AVLTree:
    """
    AVL树类：实现自平衡二叉搜索树
    提供插入、搜索、遍历等功能，确保树的高度平衡
    """
    def __init__(self):
        self.root = None

    def get_height(self, node):
        if not node:
            return 0
        return node.height

    def get_balance(self, node):
        if not node:
            return 0
        return self.get_height(node.left) - self.get_height(node.right)

    def right_rotate(self, y):
        x = y.left
        T2 = x.right

        x.right = y
        y.left = T2

        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
        x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))

        return x

    def left_rotate(self, x):
        y = x.right
        T2 = y.left

        y.left = x
        x.right = T2

        x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))

        return y

    def insert(self, root, book):
        """
        插入新节点并保持树的平衡
        :param root: 当前根节点
        :param book: 要插入的图书对象
        :return: 新的根节点
        """
        if not root:
            return AVLNode(book)
        
        if book.title < root.book.title:
            root.left = self.insert(root.left, book)
        else:
            root.right = self.insert(root.right, book)

        root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))

        balance = self.get_balance(root)

        # 左左情况
        if balance > 1 and book.title < root.left.book.title:
            return self.right_rotate(root)

        # 右右情况
        if balance < -1 and book.title > root.right.book.title:
            return self.left_rotate(root)

        # 左右情况
        if balance > 1 and book.title > root.left.book.title:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)

        # 右左情况
        if balance < -1 and book.title < root.right.book.title:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)

        return root

    def search(self, root, title):
        """
        搜索指定书名的图书
        :param root: 当前根节点
        :param title: 要搜索的书名
        :return: 找到的节点或None
        """
        if not root:
            return None
        if title == root.book.title:
            return root
        elif title < root.book.title:
            return self.search(root.left, title)
        else:
            return self.search(root.right, title)

    def inorder_traversal(self, root):
        """
        中序遍历：按书名顺序返回所有图书
        :param root: 当前根节点
        :return: 图书生成器
        """
        if root:
            yield from self.inorder_traversal(root.left)
            yield root.book
            yield from self.inorder_traversal(root.right)

class Student:
    """
    学生类：存储学生信息和借阅记录
    属性包括：学号、借阅的图书列表和信用分
    """
    def __init__(self, id):
        self.id = id
        self.books = []
        self.credit = 3
        self.next = None

class HashTable:
    """
    哈希表类：用于存储和管理学生信息
    使用链地址法处理冲突
    """
    def __init__(self):
        self.size = 100
        self.table = [None] * self.size

    def hash_function(self, key):
        return key % self.size

    def insert(self, student):
        """
        插入学生信息
        :param student: 学生对象
        """
        index = self.hash_function(student.id)
        if self.table[index] is None:
            self.table[index] = student
        else:
            current = self.table[index]
            while current.next is not None:
                current = current.next
            current.next = student

    def search(self, id):
        """
        根据学号查找学生
        :param id: 学生学号
        :return: 学生对象或None
        """
        index = self.hash_function(id)
        current = self.table[index]
        while current is not None:
            if current.id == id:
                return current
            current = current.next
        return None

class Queue:
    """
    队列类：用于管理图书预约
    使用双端队列实现
    """
    def __init__(self):
        self.queue = deque()

    def enqueue(self, item):
        """
        入队操作
        :param item: 要入队的项目
        """
        self.queue.append(item)

    def dequeue(self):
        """
        出队操作
        :return: 出队的项目或None
        """
        if len(self.queue) < 1:
            return None
        return self.queue.popleft()

class MaxHeap:
    """
    最大堆类：用于统计最受欢迎的图书
    使用堆结构实现借阅次数的排序
    """
    def __init__(self):
        self.heap = []

    def push(self, item):
        """
        添加元素到堆中
        :param item: 要添加的元素
        """
        heapq.heappush(self.heap, (-item[0], item[1]))

    def pop(self):
        """
        弹出堆顶元素
        :return: 堆顶元素
        """
        if not self.heap:
            return None
        neg_count, book = heapq.heappop(self.heap)
        return (-neg_count, book)

# 全局变量
books = AVLTree()
students = HashTable()
reservation_queue = Queue()

def load_books_from_json(json_file):
    """
    从JSON文件加载图书数据
    :param json_file: JSON文件路径
    """
    try:
        print(f"正在尝试打开文件: {json_file}")
        with open(json_file, 'r', encoding='utf-8') as f:
            print("文件打开成功，正在解析JSON...")
            data = json.load(f)
            print(f"找到 {len(data['books'])} 本书")
            
            for book_data in data['books']:
                try:
                    book = Book(
                        title=book_data['title'],
                        authors=book_data['authors'],
                        publisher=book_data['publisher'],
                        year=book_data['year'],
                        category=book_data['category'],
                        sub_category=book_data['sub_category'],
                        language=book_data['language'],
                        page_count=book_data['page_count'],
                        keywords=book_data['keywords'],
                        summary=book_data['summary']
                    )
                    books.root = books.insert(books.root, book)
                    print(f"已添加书籍: {book.title}")
                except KeyError as e:
                    print(f"警告：书籍数据缺少必要字段: {str(e)}")
                except Exception as e:
                    print(f"警告：处理书籍数据时出错: {str(e)}")
            
            print("所有书籍添加完成！")
            
            # 验证数据加载
            book_count = sum(1 for _ in books.inorder_traversal(books.root))
            print(f"AVL树中实际存储的书籍数量: {book_count}")
            
    except FileNotFoundError:
        print(f"错误：找不到文件 {json_file}")
        print("请确保文件存在并且路径正确")
    except json.JSONDecodeError as e:
        print(f"错误：JSON解析失败 - {str(e)}")
        print("请检查JSON文件格式是否正确")
    except Exception as e:
        print(f"加载数据时发生错误: {str(e)}")
        print(f"错误类型: {type(e).__name__}")

def search_book(title):
    """
    搜索图书
    :param title: 书名
    :return: 图书对象或None
    """
    node = books.search(books.root, title)
    return node.book if node else None

def borrow_book(student_id, book_title):
    """
    借阅图书
    :param student_id: 学生学号
    :param book_title: 书名
    :return: 是否借阅成功
    """
    student = students.search(student_id)
    if not student:
        student = Student(student_id)
        students.insert(student)
    
    if len(student.books) >= 7:
        return False
    
    book = search_book(book_title)
    if not book or book.is_borrowed:
        return False
    
    book.is_borrowed = True
    book.borrow_count += 1
    student.books.append(book)
    return True

def return_book(student_id, book_title):
    """
    归还图书
    :param student_id: 学生学号
    :param book_title: 书名
    :return: 是否归还成功
    """
    student = students.search(student_id)
    if not student:
        return False
    
    book = search_book(book_title)
    if not book or not book.is_borrowed:
        return False
    
    if book in student.books:
        book.is_borrowed = False
        student.books.remove(book)
        return True
    return False

def lost_book(student_id, book_title):
    """
    报失图书
    :param student_id: 学生学号
    :param book_title: 书名
    :return: 是否报失成功
    """
    student = students.search(student_id)
    if not student:
        return False
    
    book = search_book(book_title)
    if not book or not book.is_borrowed:
        return False
    
    if book in student.books:
        book.is_borrowed = False
        student.books.remove(book)
        student.credit -= 1
        return True
    return False

def generate_statistics():
    """
    生成图书借阅统计
    :return: 最受欢迎的图书列表
    """
    max_heap = MaxHeap()
    for book in books.inorder_traversal(books.root):
        max_heap.push((book.borrow_count, book))
    
    result = []
    while True:
        item = max_heap.pop()
        if not item:
            break
        result.append(item[1])
    
    return result

# 测试代码
if __name__ == "__main__":
    # 获取当前文件所在目录
    current_dir = os.path.dirname(os.path.abspath(__file__))
    json_path = os.path.join(current_dir, "books.json")
    
    print(f"当前工作目录: {os.getcwd()}")
    print(f"尝试加载文件: {json_path}")
    
    # 加载测试数据
    load_books_from_json(json_path)
    
    # 测试借阅功能
    print("\n测试借阅功能:")
    if books.root:
        # 获取第一本书
        first_book = next(books.inorder_traversal(books.root))
        print(f"尝试借阅书籍: {first_book.title}")
        print(borrow_book(1, first_book.title))
    else:
        print("没有可用的书籍进行测试")
    
    # 测试归还功能
    print("\n测试归还功能:")
    if books.root:
        first_book = next(books.inorder_traversal(books.root))
        print(f"尝试归还书籍: {first_book.title}")
        print(return_book(1, first_book.title))
    else:
        print("没有可用的书籍进行测试")
    
    # 测试统计功能
    print("\n测试统计功能:")
    popular_books = generate_statistics()
    if popular_books:
        print("最受欢迎的图书:")
        for book in popular_books[:5]:
            print(f"书名: {book.title}, 借阅次数: {book.borrow_count}")
    else:
        print("没有可用的书籍进行统计") 